
'''
# 构造一个队列(先进先出)
# class Queue(object):
#     def __init__(self):
#         self.queue = []
#
#     def enqueue(self,item):
#         self.queue.append(item)
#
#     def dequeue(self):
#         return self.queue.pop(0)
#
#     def is_empty(self):
#         return self.queue == []
#
#     def size(self):
#         return len(self.queue)
'''

'''
# 构造一个栈（后进先出）
# class Stack(object):
#     def __init__(self): # 创建一个新的空栈
#         self.stack = []
#
#     def push(self,item): # 添加新元素到栈顶
#         self.stack.append(item)
#
#     def pop(self):  # 弹出栈顶元素
#         return self.stack.pop()
#
#     def peek(self):  # 返回栈顶元素
#         return self.stack[-1]
#
#     def is_empty(self): # 判断栈是否为空
#         return self.stack == []
#
#     def size(self): # 返回栈的元素个数
#         return len(self.stack)

'''


# 括号匹配问题
# def math(s):
# 	match = {'}':'{',']':'[',')':'('}  # 对应关系
# 	stack = []
# 	for i in s:
# 		if i in ['{','[','(']:
# 			stack.append(i)
# 		else:
# 			if stack == []:
# 				return False
# 			elif stack[-1] == match[i]:
# 				stack.pop()
# 			else:
# 				return False
# 	return stack == []

# print(math('[{[({})][]}]()'))



'''

# 深度优先搜索（回溯法）
maze = [
	[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
	[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
	[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
	[1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
	[1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
	[1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
	[1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
	[1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
	[1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
	[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

dirs = [
	lambda x, y: (x+1, y),
	lambda x, y: (x-1, y),
	lambda x, y: (x, y-1),
	lambda x, y: (x, y+1)
]

def maze_path(x1,y1,x2,y2):
	stack = []
	stack.append((x1,y1))
	while stack:
		curNode = stack[-1] # 尾节点
		if curNode[0] == x2 and curNode[1] == y2:
			print(stack)
			return True
		for dir in dirs:
			nextNode = dir(curNode[0],curNode[1])
			# 如果下一个节点能走
			if maze[nextNode[0]][nextNode[1]] == 0:
				stack.append(nextNode)
				maze[nextNode[0]][nextNode[1]] = 2  # 标记为走过
				break
		else:
			maze[curNode[0]][curNode[1]] = 2
			stack.pop()
	else:
		print('没录了')
		return False

maze_path(1,1,8,8)
print(maze)


from collections import deque
# 广度优先遍历

def print_r(path):
	curNode = path[-1]
	realpath = []
	while curNode[2] != -1:
		realpath.append((curNode[0:2]))
		curNode = path[curNode[2]]
	realpath.append(curNode[0:2])  # 把起点放进去
	realpath.reverse()  # 把路线倒序
	print(realpath)


def maze_path_queue(x1,y1,x2,y2):
	queue = deque()
	queue.append((x1,y1,-1))
	path = []
	while queue:
		curNode = queue.popleft()
		path.append(curNode)
		if curNode[0] == x2 and curNode[1] == y2:
			# 终点
			print_r(path)
			return True
		for dir in dirs:
			nextNode = dir(curNode[0],curNode[1])
			if maze[nextNode[0]][nextNode[1]] == 0:
				queue.append((nextNode[0],nextNode[1],len(path)-1))
				maze[nextNode[0]][nextNode[1]] = 2
	else:
		print('没路了')
		return False

maze_path_queue(1,1,8,8)

'''